package DataStructuresTest.ArrayListTest;

import java.util.Arrays;

/**
 * 可增长数组
 * 优点：对get和set调用花费常数时间
 * 缺点：新项的插入和现有的项的删除单价昂贵
 * @param <AnyType>
 */
public class MyArrayList<AnyType> implements Iterable<AnyType>{
    private static final int DEFAULT_CAPACITY = 10;

    //MyArrayList把大小及数组作为其数据成员进行存储
    private int theSize;
    private AnyType [] theItems;

    //初始化MyArrayList
    public MyArrayList(){doClear();}

    //清理
    public void clear(){doClear();}

    private int size() {return theSize;}
    public boolean isEmpty(){return size() == 0;}
    public void trimToSize(){ensureCapacity(size());}

    private void doClear() {theSize = 0;ensureCapacity(DEFAULT_CAPACITY);}

    public AnyType get(int idx){
        if (idx < 0 || idx >= size())throw new ArrayIndexOutOfBoundsException();
        return theItems[idx];
    }

    /**
     * 设置方法
     * @param idx 需要设置数据的下标
     * @param newVal 需要设置的数据元素
     * @return
     */
    public AnyType set(int idx,AnyType newVal){
        if (idx < 0 || idx >= size())throw new ArrayIndexOutOfBoundsException();
        AnyType old = theItems[idx];
        theItems[idx] = newVal;
        return old;
    }

    /**
     * 扩容方法
     * @param newCapacity ArrayList扩容后的大小
     */
    private void ensureCapacity(int newCapacity) {
        //ensureCapacity也可以用于收缩基础数组，只有当指定的新容量至少和原大小一样才适用
        if (newCapacity < theSize)return;
        
        //存储对原始数组的一个引用
        AnyType [] old = theItems;
        //为新数组分配内存。由于泛型数组的创建是非法的所以先创建一个泛型类型限界的数组，然后使用一个数组进行类型转换
        theItems = (AnyType [])new Object[newCapacity];
        for (int i = 0; i < size(); i++) {
            //将旧内容拷贝到新数组中
            theItems[i] = old[i];
        }
    }

    /**
     * 添加方法是否成功执行
     * @param x 需要添加的数据元素
     * @return
     */
    public boolean add(AnyType x){
        add(size(),x);
        return true;
    }

    /**
     * 添加数据方法
     * @param idx 需要添加的元素所在的下标，从以当前ArrayList长度的为下表
     * @param x 需要添加的元素
     */
    public void add(int idx,AnyType x){
        if (theItems.length == size())
            ensureCapacity(size()*2+1);
        for (int i = theSize; i > idx; i--) {
            theItems[i] = theItems[i-1];
        }
        theItems[idx] = x;

        theSize++;
    }

    public AnyType remove(int idx){
        AnyType removedItem = theItems[idx];
        for (int i = idx; i < size(); i++) {
            theItems[i] = theItems[i+1];
        }

        theSize--;
        return removedItem;
    }

    @Override
    public String toString() {
        return "MyArrayList{" +
                "theSize=" + theSize +
                ", theItems=" + Arrays.toString(theItems) +
                '}';
    }

    /**
     * 这个类将存储迭代序列中的下一项的下标
     * 提供next，hasNext，remove等方法的实现
     * iterator直接返回ArrayListIterator类的一个实例
     * ArrayListIterator存储当前位置的概念
     * @return
     */
    public java.util.Iterator<AnyType> iterator(){return new ArrayListIterator();}

    private class ArrayListIterator implements java.util.Iterator<AnyType>{
        private int current = 0;
        public boolean hasNext(){ return current < size(); }

        public AnyType next(){
            if (!hasNext())throw new java.util.NoSuchElementException();
            return theItems[current++];
        }

        public void remove(){MyArrayList.this.remove(--current);}
    }
}
